package Demo3;


import java.util.Arrays;

public class HamiltonCycle {
    private int V;//图中结点个数
    private int[] path;//存储路径，数组表示
    private int[][] graph;//图的邻接矩阵
    //初始化图
    public HamiltonCycle(int[][] graph){
        this.graph=graph;
        this.V=graph.length;
        this.path=new int[V];//这条路径的长度就是结点个数
        //将路径数组全部填充为-1
        Arrays.fill(path,-1);
    }

    //递归遍历所有可能的结点顺序
    public void FindHamilton(int[] path,int pos){
        //如果当前路径长度等于结点个数
        if (pos==V){
            //检查是否存在从最后一个结点到第一个结点的边
            //path[pos-1]表示最后一个结点，path[0]表示第一个结点
            if (graph[path[pos-1]][path[0]]==1){
                printPath(path);
            }
            return ;
        }
        for (int v=1;v<V;v++){

        }
    }

    //判断当前结点是否可以加入到路径中
    public boolean isValid(int v,int[] path,int pos){
        if (graph[path[pos-1]][v]==0){
            return false;
        }
        for (int i=0;i<pos;i++){
            if (path[i]==v){
                return false;
            }
        }
        return true;
    }

    //打印路径
    public void printPath(int[] path){
        for (int vertex:path){
            System.out.print(vertex+"->");
        }
        System.out.println(path[0]);
    }
}
